#include <stdio.h>

int Fib1(int n){
    if(n < 1){
        return -1;
   }else if( n == 1 || n == 2){
       return 1;
   } else {
       return Fib1(n - 1) + Fib1(n - 2);
   }
}

long Fib2(int n){
    if(n < 1){
        return -1 ;
    }
    long a[n + 1];
    a[1] = 1;
    a[2] = 1;
    for(int i = 3; i <= n; i++){
        a[i] = a[i - 1] + a[i - 2];
    }

    return a[n];
    
}

double loop(int n, double result_of_n_1, double result_of_n_2){
    if(n == 3){
        return result_of_n_1 + result_of_n_2;
    } else{
        return loop(n - 1, result_of_n_1 + result_of_n_2, result_of_n_1);
    }
}

double Fib3(int n){
    if(n < 1){
        return -1;
    } else if(n == 1 || n == 2){
        return 1;
    } else {
        return loop(n, 1, 1);
    }
}

// 迭代法
double Fib4(int n){
    if(n < 1){
        return -1;
    }

    if(n == 1 || n == 2){
        return 1;
    }
    
    double s1, s2;
    s1 = 1;
    s2 = 1;
    for(int i = 3; i<=n; i++){
        s2 = s1 + s2;
        s1 = s2 - s1;
    }
    return s2;
}

int main(){
    printf("Fib(1000)=%f", Fib4(1000));
    return 0;
}